編譯器做了什麼?

我們知道使用機器指令撰寫程式碼是非常麻煩的事情，也會使開發程式的效率不高，編譯器就是將來源碼（source code）翻譯成機器語言（object code）的一種工具。

Source Code 到 Object Code 中間發生了什麼事情

Complier 會分三個階段

1.Front-end: 將程式碼切成一個一個的字，然後照該語言的邏輯變成一個抽象語法樹(AST)
2.Middle-end: 將AST轉換成中間語言(IR),並優化這個IR
3.Back-end:將IR 轉換成目標碼並且優化

詞彙分析(Lexical analysis)

首先將 來源碼 (Source Code) 輸入到 掃描器(Scanner)，掃描器只是簡單地進行語法分析，使用一種類似於有限狀態機(Finite State Machine) 的算法將 Source Code 的字符序列分割成一系列的 Token。

unsigned background(unsigned foreground) {
    if ((foreground >> 16) > 0x80) {
        return 0;
    } else {
        return 0xffffff;
    }
}

有一個叫做lex 的程序可以實現詞法掃描，他會按照描述好的詞彙規則將輸入字符分割成一個個的Token，編譯器的開法者就無需對每個編譯器開發一個獨立的掃描器，而是根據需要改變語法規則就可以了

語法分析 (Parser)

Parser 讀取 token，然後對照語法規則來判斷 token 屬於哪個語法的哪個部分，遇到不合法的 token 就會丟出 Parse error，最後產生語法樹(Synta Tree)

那麼語法規則該怎麼表示呢?
是一種用來表示上下文無關文法的語言，原理非常複雜，因此不贅述，定義了語法之後，我們就可以拿這個文法來實作真的parser 程式碼，Parser 使用 LL 或 LR 兩種方式轉換語法樹，而通常在現代 parser generator 的技術都很成熟了，只要把 CFG 定義好丟給 parser generator 就可以產生 parser 了。

語意分析 (Semantic analysis)

語意分析是根據語言規則和上下文，檢查 parse tree 裡的語意是否有問題。

var a:bool = 1 + ture

假設一個數字跟一個布林值相加，很明顯是錯誤的，Semantic analysis 要做的就是把這個問題抽出來，可能不只這些語意上錯誤，不同語言也可能有不同的規則，而編譯器所能分析的語意是靜態語意，所謂的靜態語意是指在編譯期間可以確定的語意，與之對應的動態語意就是只有在運行期間才可以確定的語意。

中間語言 (Intermediate code)

編譯器可能有中間語言，稱作中間表達式 Intermedia Representation（簡稱 IR），以便進行後續的優化以及對應多機器平台的機器碼。

為什麼需要先轉為 IR 優化後才轉為 Object Code？

1.如果沒有 IR，直接從 Front-end 編譯到各個機器平台的話，因為對應平台的機器目的碼都不同，這樣會有太多種的組合，以實作來說就是一個悲劇。而 IR 通常都是不相依於機器的，因此這樣更易於重用，提高開發彈性。
2.直接在語法樹上做優化較其困難，所以將 Source Code 優化器往往講整個語法樹轉換成 IR ，它是語法樹的順序表示。

程式碼生成（Code Generation）

程式碼生成器將IR轉換成機器碼，這個過程十分依賴於目標機器，因為不同機器有著不同的CPU架構而有不同的指令集，另外也有一種虛擬機 (VM, Virtual Machine)，主要是建立跨平台的執行環境，讓相同的目標碼在任何機器上執行，像是 JVM 它的目標碼就是 bytecode 。
最後目標碼優化器對上述機器碼進行優化，這邊屬於跟機器平台有關的優化，往往利用硬體平台的特性來幫助優化，IR的優化屬於與機器無關的優化。

參考資料

实现一个编译器需要实现哪些流程？
人人都能读懂的编译器原理
一點都不深入的了解 Compiler、 Interpreter 和 VM